a. Field of the Invention
The present invention concerns a method for designing a robust, highly reliable, and survivable communications network, and in particular, for designing or routing a self-healing ring in a network that complies with the SONET (or Synchronous Optical Network) protocol. The present invention also concerns a robust, highly reliable, and survivable communications network designed in accordance with the method.
b. Related Art
SONET is an optical transmission protocol intended to exploit the high-speed digital transmission capability of optical fiber. SONET was originally proposed by BellCore and standardized by the American National Standards Institute (or ANSI). Thus, SONET establishes an optical-signal standard for interconnecting equipment from different vendors. Although the SONET protocol is known to those skilled in the art, its salient features are briefly described below for the reader's convenience.
SONET provides a standard hierarchy of time division multiplexed digital transmission rates that accommodates existing North American and CCITT (Consultative Committee for International Telephone and Telegraph) transmission rates. As shown in the table of FIG. 1, this hierarchy uses 51.84 Mbps building blocks. In FIG. 1, the "OC", preceding a number "n", stands for the "Optical Carrier" level and the number "n" indicates a multiple of the 51.84 Mbps basic transmission rate. Also, in FIG. 1, the "STS" (or Synchronous Transport Signal) level corresponds to the OC level before the bit stream has been converted to an optical signal. Finally, as shown in FIG. 1, the CCITT rates start at STM-1 (Synchronous Transfer Mode-level 1) which corresponds to an OC-3 or 155.52 Mbps signal.
FIG. 2a is a block diagram of a connection of two (2) SONET terminals 202 and 204. As shown in FIG. (a), the SONET standard may be mapped into a four (4) layer logical hierarchy which includes (i) a photonic layer 210, (ii) a section layer 212, (iii) a line layer 214, and (iv) a path layer 216.
The photonic layer 210 is the physical layer. It specifies, for example, the type of optical fiber that may be used, the required minimum powers and dispersion characteristics of the transporting lasers, and the required sensitivity of the receivers. The photonic layer 210 is also responsible for converting STS (i.e., electrical) signals to OC (i.e., optical) signals.
The section layer 212 creates the basic SONET frames, which are described in greater detail below. It also specifies transmission functions such as framing, scrambling, and error monitoring. The line layer 214 is responsible for synchronizing and multiplexing data onto the SONET frames and for line protection switching. Finally, the path layer is responsible for end-to-end transport of data at the appropriate signaling speed.
FIG. 2b is a block diagram that shows a physical implementation corresponding to the four (4) logical layers discussed above. A section 240 represents a single run of optical cable between two (2) optical-fiber transmitter/receivers. For relatively short runs, the cable may run directly between two end units 202 and 204. However, for longer distances, repeaters 206 are needed. A repeater 206 regenerates and repeats a received stream of digital data.
A line 250 is a sequence of one or more sections 240. Within a line 250, the internal signal or channel structure of the signal remains constant. End points 208 and switches/multiplexers 230 may add or drop channels. An "add/drop network" includes add/drop multiplexers that permit standard DSn or SONET signals to be added to, or dropped from, a line signal. SONET add/drop nodes or multiplexers perform a function similar to traditional back-to-back multiplexers, except that through circuits are more economically cross-connected electronically (instead of being electrically patched together at a DSX panel and requiring interface circuit packs). Add/drop multiplexers are discussed in more detail below with reference to FIGS. 8 and 9.
Finally, a path 260 connects two end terminals 202, 204 and corresponds to an end-to-end circuit. Data are assembled at one end of a path 260 and are not or modified until they are disassembled at the other end of the path 260.
As discussed above with reference to FIG. 2a, the section layer 212 creates the basic SONET frames. As shown in FIG. 3, an STS-1 frame format 300 can logically be viewed as a matrix of nine (9) rows 302, each row having 90 octets 304. The STS-1 frame is transmitted one row at a time, from left to right and top to bottom. The 810 octets defining the STS-1 frame 300 are transmitted every 125 .mu.s for an overall transmission rate of 51.84 Mbps.
As is further illustrated in FIG. 3, the first three columns 308 of the STS-1 frame 300 are reserved for transport overhead information. Specifically, the first three octets of the first three rows include section 240 overhead information 310, the first three octets of the fourth row include pointer data, and the first three octets of the fifth through ninth rows include line 250 overhead information 320.
More specifically, the first three octets of the first three rows 308 include "regenerator section overhead" information 310. This information may be used by SONET repeaters that renew the SONET signal. As shown in FIG. 4, octets 402 are framing bytes (F6, 28 hex) which are used to synchronize the beginning of the frame 300. Octet 404 is an STS-ID byte that identifies the STS-1 number for each STS-1 within an STS-N multiplex. Octet 406 is a bit-interleaved parity byte providing even parity over the previous STS-N frame after scrambling. The i.sup.th bit of this octet 406 contains the even parity value calculated from the i.sup.th bit position of all octets in the previous frame. Octet 408 is a section-level 64 Kbps PCM (pulse code modulation) orderwire that may be used to provide an optional voice channel between section terminating equipment, hubs and remote terminals. (An "orderwire" is a circuit used by a telephone company for establishing voice contact between a node and carrier repeater locations.) Octet 410 is an undefined 64 Kbps channel that may be used for user defined purposes. The three octets 412 define a 192 Kbps data communication channel for alarms, maintenance, control, and administration between sections 240.
The first three octets of the forth row 414 define pointers that indicate where, within the payload, the data starts. These pointers are needed because the SONET protocol permits data to start at an arbitrary byte in the payload. These pointers 414 permit frame alignment and frequency adjustment of the payload data. The pointers 414 may also point to one of the 90 columns 330 used for multiplexing information within the data (or "path overhead"). The path overhead 330 is described in detail below.
The first three octets of the fifth through ninth rows define "multiplexer section overhead" information 320. This information is used by SONET multiplexers that combine and extract individual data channels from within the SONET frames 300. Octet 416 is a bit-interleaved parity byte for line-level error monitoring. Octets 418 are allocated for signaling between line-level automatic-protection switching equipment. Line protection switching will be described in more detail below. Specifically, they use a bit-oriented protocol that provides error protection and management of the SONET optical link. Octets 420 provide a 576 Kbps data communication channel for alarms, maintenance, control, monitoring and administration at the line 250 level. The octets 422 are reserved for future use. Finally, octet 424 is a 64 Kbps PCM voice channel for line-level orderwire.
As shown in FIG. 4, the path overhead 330 is formed by a column of nine octets. Octet 426 is a 64 Kbps channel used to repetitively send a user programmable 64-octet fixed-length string so a receiving terminal can continuously verify the integrity of a path. Octet 428 is a bit interleaved parity byte at the path level, calculated over all bits of the previous synchronous payload envelope (or SPE). Octet 430 designates whether the STS signal is "equipped" or "unequipped." An equipped STS signal has a line connection and path data to send. This octet 430 can be used to indicate the specific STS payload mapping that may be needed in receiving terminal to interpret the payload. In an unequipped STS signal, a line connection is complete but there are no path data to send. Octet 432 is a status byte, sent from path-terminating equipment back to path-originating equipment, which conveys the status of the terminating equipment and path error performance. Octet 434 is a 64 Kbps user definable channel. Octet 436 is a multiframe indicator for payloads that may not be carried on a single STS frame. Octets 438 are reserved for future use.
To reiterate, the SONET protocol is intended to exploit the high-speed digital transmission capability of optical fiber. To economically use optical fiber within a communications network, the network is often organized as a hubbing structure based on a "single homing" concept. With single homing, the communications between an office within the hub and an office outside the hub, are routed through an associated home hub. Unfortunately, hubbing network architectures are inherently vulnerable in the event of fiber cuts or major hub failures. This vulnerability, together with the high traffic capacity of optical fiber, increases the need for robust, survivable network architectures.
Optical fiber networks using the SONET protocol often include add/drop multiplexers 800. As shown in FIG. 8, an add/drop multiplexer 800 includes a time-slot assignment fabric 802 which permits flexible reassignment of time slots. This flexible reassignment of time slots permits the add/drop multiplexer 800 to be provisionable (locally or remotely) to (i) add traffic from a tributary 810 to a communications channel 806, and/or 808', via a tributary card 804, (ii) drop traffic from a communications channel 806 or 808 to a tributary 810, via a tributary card 804, and (iii) pass through traffic from communications channel 806 to 806' and/or from communications channel 808 to 808'.
As shown in greater detail in FIG. 9, an exemplary add/drop multiplexer 800 includes a time-slot assignment fabric 802 and tributary cards 804. In the time-slot assignment fabric 802, an incoming OC-48 signal 806 or 808 is converted to an electrical STS-48 signal by converter 902b or 904b, respectively, and demultiplexed by demultiplexer 908a or 908b, respectively, to provide 16 STS-3 signals. Any of the 16 STS-3 signals to be dropped are demultiplexed by demultiplexer 910b or 910a and passed to a tributary card 804 where a selector 912b or 912a and interface card 914b or 914a passes a selected one of the signals (i.e., a non-faulty signal) to switch 916. Any of the 16 STS-3 signals to pass through are remultiplexed by multiplexers 910a and 910b and multiplexers 906a and 906b to construct part of outgoing STS-48 signals. The outgoing STS-48 signals are converted to OC-48 signals 808' and 806' by converter 902a or 904a. Signals to be added are provided to a tributary card 804, via a switch 916 where a generator (not shown) passes it to multiplexers 910a and 910b and multiplexers 906a and 906b to construct part of outgoing STS-48 signals. The STS-48 signals are converted to OC-48 signals 808' and 806' by converters 902a and 904a.
Recently, self-healing architectures are becoming increasingly used by network providers to meet user demands for network reliability and survivability. More particularly, the add/drop functionality encouraged by the SONET protocol has made the use of self-healing rings (or SHRs) popular. Although the use of self-healing rings in SONET networks is known (See e.g., the article, Haque et al., "Self-Healing Rings in a Synchronous Environment," IEEE LTS, (November 1991), modified and reprinted in SONET SDH: A Sourcebook of Synchronous Networking, pp. 131-139 (Edited by Siller and Shafi) (1996)), which is incorporated by reference herein), a brief discussion of self-healing rings in SONET networks is provided below for the reader's convenience.
In a self-healing ring network, traffic between two points is carried in an add/drop network that is looped back on itself to form a ring. Such a ring offers protection against fiber cuts or node failures by providing an alternative path which bypasses the cut fiber or failed node. In a ring add/drop architecture, there are no terminal nodes (or central office), and each node (or central office) has add/drop functionality.
Ring architectures may be classified based on (i) the directionality of service routing and (ii) the protection mechanism. Regarding the directionality of the service routing in the ring, a unidirectional ring carries service traffic in only one direction (i.e., only clockwise or only counterclockwise) of the ring. On the other hand, a bi-directional ring carries service traffic in both directions (i.e., clockwise and counterclockwise) on the ring. Regarding the protection mechanism of the ring, a path-switched ring protects traffic based on the health of each individual path where the path exits the ring, (see e.g. elements 216 and 224 of FIG. 2a and element 260 of FIG. 2b). On the other hand, a line-switched ring protects traffic based on the health of the line between each pair of nodes (see e.g., elements 214 and 222 of FIG. 2a and elements 250 of FIG. 2b) and when a line is faulty, the entire line is switched to a protection loop at the boundaries of the faulty line.
Based on the above two categories of directionalities of service routing and protection mechanisms, two ring architectures have become preferred for use in SONET networks; namely (i) two-fiber unidirectional path-switched rings and (ii) two-fiber and four-fiber bi-directional line-switched rings. Although each of these ring architectures is understood by those skilled in the art, each is briefly described below for the reader's convenience.
FIG. 5a is a block diagram which illustrates a two-fiber unidirectional path-switched ring in which a number of nodes (or central offices) 502, 504, 506, 508 and 510 are connected in a ring with a service fiber 512 and a protection fiber 514. As shown in FIG. 5a, the service fiber 512 routes traffic within the ring in a clockwise direction while the protection fiber 514 routes traffic within the ring in a counterclockwise direction. Thus, a transmission 516 from node (or central office) A 502 to node (or central office) C 506 is carried by the service fiber 512 to node C in a clockwise direction. The signal 516 is also fed to the protection fiber 514 which carries it to node C 506 in a counterclockwise direction. As shown in FIG. 5a, in normal operation, at node C, the signal 516' is taken (or "dropped") from the service fiber 512. (Recall the selectors 912a and 912b of FIG. 9.) Similarly, transmission 518 from node C 506 to node A 502 is carried by the service fiber 512 in a clockwise direction and by the protection fiber 514 in a counterclockwise direction. In normal operation, at node A, the signal 518' is taken ("dropped") from the service fiber 512.
Each path is individually switched based on signal health. For example, as shown in FIG. 5b, if the service fiber 512 between node B 504 and node C 508 is cut, then a transmission 516 from node A 502 to node C 506 cannot reach node C 506 via the service fiber 512. That is, the path between nodes A 502 and C 506 is faulty. Thus, at node C 506, the signal 516" is taken (or "dropped") from the protection fiber 514, not the service fiber 512 because the path from node A 502 to node C 506 is faulty. However, the cut in the service fiber 512 between node B 504 and node C 506 does not affect the health of the service fiber path 512 from node C 506 to node A 502. Thus, at node A 502, the transmission 518" from node C 506 to node A 502 is taken from the service fiber 512, not the protection fiber 514.
In the two-wire unidirectional path-switched ring, each signal entering the ring is carried all the way around the ring. Thus, the amount of traffic on the ring is the sum of all traffic entering the ring.
FIG. 6 is a block diagram which illustrates a four-wire bi-directional line-switched ring in which a number of nodes (or add/drop multiplexers) 502, 504, 506, 508, and 510 are coupled in a ring with a two service fibers 612 and two protection fibers 614. One of the service fibers 612a carries traffic in a clockwise direction while the other service fiber 612b carries traffic in a counterclockwise direction. Similarly, one of the protection wires 614a carries traffic in a clockwise direction while the other protection fiber 614b carries traffic in a counterclockwise direction.
The operation of the four wire bi-directional line-switched ring is described with reference to FIG. 6. To transmit a message from node A 602 to node C 606 for example, node A is provisioned as an "add" node, intermediate nodes B 604, or E 610 and D 608, are provisioned as "through" nodes, and node C 606 is provisioned as a "drop" node.
Receiver, transmitter or single fiber failures can be protected by normal span protection. For example, if a service fiber 612a and/or 612b is cut at point 616, span switches (at Node A 602 and at Node B 604) will move the service from the service fiber 612a and/or 612b to the protection fiber 614a and/or 614b and back to the service fiber 612a and/or 612b as shown by the phantom lines 618. With such span-switching, the service between the other nodes is unaffected.
In the case of a complete fiber cut or a node failure, a line switch (such as an automatic protection switching system or "APS", for example) is used to perform a ring loop back function. For example, if the service 612 and protection 614 fibers are cut at point 620, Node D 608 will loop the counterclockwise protection fiber 614b back to the clockwise protection fiber 614a and will loop the counterclockwise service fiber 612b back to the clockwise service fiber 612a as shown by phantom lines 622. Similarly, Node C 606 will loop the clockwise protection fiber 614a back to the counterclockwise protection fiber 614b and will loop the clockwise service fiber 612a back to the counterclockwise service fiber 612b as shown by phantom lines 624. In the event of a node failure, such as by Node C 606 for example, Nodes B 604 and D 608 would both perform a loop back.
FIG. 7 is a block diagram of a two-fiber bi-directional path-switched ring which includes nodes (or central offices) 702, 704, 706, 708, and 710 with two physical fibers 712 and 714. In this ring, the capacity of a first fiber 712 is logically divided into a service portion and a protection portion. Both the service portion and the protection portion of the first fiber 712 route traffic in a clockwise direction. Similarly, the capacity of a second fiber 714 is logically divided into a service portion and a protection portion. Here, both the service portion and protection portion of the second fiber 714 route traffic in a counterclockwise direction. This ring can survive in the event of receiver, transmitter, fiber or node failure by providing a ring line loop back function similar to that described above with reference to FIG. 6. Specifically, if the clockwise fiber 712 and/or the counterclockwise fiber 714 was cut at point 720, Node D 708 would loop the counterclockwise fiber 714 back to the clockwise fiber 712 as shown by phantom line 722. Similarly, Node C 706 would loop the clockwise fiber 712 back to the counterclockwise fiber 714 as shown by phantom line 724. If a node, such as Node C 706 were to fail, both Nodes B 704 and D 708 would perform a loop back. However, electronics failures cannot be protected against with a span switch, as was the case with the four-fiber, bi-directional, path-switched ring of FIG. 6.
In the design and implementation of each of the above discussed types of self-healing ring architectures, and in other self-healing ring architectures as well, the cost of implementing the ring, known as "fiber transport cost," is a significant factor. The fiber transport cost includes costs for terminating equipment (e.g., multiplexers), fiber material (e.g., the optical fiber), and fiber placement (e.g., regenerators, licensing fees, etc.). When a ring is to be implemented in an existing network, certain nodes are specified as ring offices. Minimizing the cost to implement (or "route") a ring including the ring offices is a complex problem.
Methods for minimizing the costs for implementing a survivable fiber network, such as a self-healing ring network are known. For example, the article, Wasem, "An Algorithm for Designing Rings for Survivable Fiber Networks," IEEE Transactions on Reliability, Vol. 40, No. 4, pp. 428-432 (October 1991) (hereinafter referred to as "the Wasem article") discusses a method for routing fiber around a ring in a network. Given a network in which certain nodes (or central offices) are to be part of a self-healing ring, the Wasem article first tries a crude or rudimentary method to find a ring including each of the "ring" offices. If the crude method fails, a "greedy" heuristic (which is more complex than the crude method) is tried. A "greedy" heuristic is one which seeks to provide optimal local solutions at each step of the heuristic but does not necessarily provide an optimal global solution.
In the crude method, a hub ring office and a ring office furthest from the hub ring office are first determined. Next, two iterations of the Dijkstra shortest path algorithm are performed to find the two shortest, link disjoint paths (i.e., communications channels or paths sharing no common links) between the hub ring office and the furthest ring office. A ring is routed if the paths are node disjoint (i.e., share no common node) and if the cycle (or ring) formed includes all of the ring offices. If a ring cannot be routed, the greedy heuristic is tried.
In the greedy heuristic discussed in the Wasem article, a depth-first search for paths between all pairs of ring offices, in which the paths contain only two ring offices, is performed until a path length threshold is exceeded or the number of hops (i.e., number of links) in paths exceeds a threshold. After the paths are determined, different combinations of node disjoint paths are used to try to construct a ring. Specifically, starting at an office, the shortest path out which terminates at a next office is tried and so on until either (a) a ring is formed or (b) no more node disjoint paths are available. If no more node disjoint paths are available, the method starts at a new office and tries different path combinations. If still no ring is formed, the distance threshold is increased until the path distance increases to the point that a signal regenerator is needed.
Although the method discussed in the Wasem article can be used to find rings, the rings it constructs are often not even close to an optimum ring which minimizes fiber transport costs. Moreover, the "greedy" heuristic espoused in the Wasem article has a relatively slow run time, particularly for "dense" networks. (The "density" of a network corresponds to the number of different links between central offices. For example, in the New York-New England area, the Eastern Massachusetts network is relatively dense while the Rhode Island network is relatively sparse.) Thus, a new method is needed to design or route optimum or near-optimum rings in a network. The new method should be relatively quick, particularly when rings are to be found in dense networks.